package basic.study.wantOffer.chapter5;

/**
 * @ClassName Problem47
 * @Description
 * @Company inspur
 * @Author Kevin
 * @Date 2020/6/4 17:43
 * @Version 1.0
 */
public class Problem47 {
    class MaxValueOfGifts {
        public int maxValueOfGifts(int[][] values) {
            if (values == null || values.length <= 0 || values[0].length <= 0) {
                return 0;
            }
            int rows = values.length;
            int cols = values[0].length;
            int[][] maxValues = new int[rows][cols];
            for (int i = 0; i < rows; i++) {
                for (int j = 0; j < cols; j++) {
                    int up = 0;
                    int left = 0;
                    if (i > 0) {
                        left = maxValues[i-1][j];
                    }
                    if (j > 0) {
                        up = maxValues[i][j-1];
                    }
                    maxValues[i][j] = Math.max(left, up) + values[i][j];
                }
            }
            return maxValues[rows-1][cols-1];
        }
    }
}
